package com.zyk.leetcode;

import com.zyk.util.TreeUtil;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author zhangsan
 * @date 2021/4/16 17:43
 */
public class C107 {


    // BFS
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        LinkedList<List<Integer>> ans = new LinkedList<>();
        if (root == null) return ans;
        List<Integer> level = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>() {{
            add(root);
        }};
        TreeNode end = root, nextEnd = root, cur;
        while (!queue.isEmpty()) {
            cur = queue.poll();
            level.add(cur.val);
            if (cur.left != null) {
                queue.add(cur.left);
                nextEnd = cur.left;
            }
            if (cur.right != null) {
                queue.add(cur.right);
                nextEnd = cur.right;
            }
            if (end == cur) {
                ans.addFirst(level);
                level = new ArrayList<>();
                end = nextEnd;
            }
        }
        return ans;
    }

    private List<List<Integer>> ans;

    // DFS
    public List<List<Integer>> levelOrderBottom2(TreeNode root) {
        ans = new ArrayList<>();
        if (root == null) return ans;
        dfs(root, 0);
        return ans;
    }

    public void dfs(TreeNode root, int level) {
        if (root != null) {
            if (ans.size() <= level) {             // 先序玩, 有个高度的参数
                ans.add(0, new ArrayList<>());
            }
            ans.get(ans.size() - level - 1).add(root.val);
            dfs(root.left, level + 1);
            dfs(root.right, level + 1);
        }
    }


    // for test
    public static void main(String[] args) {
        C107 test = new C107();

        Integer[] treeVal = {3, 9, 20, null, null, 15, 7};
        TreeNode tree = TreeUtil.generateTreeByArr(treeVal);
        List<List<Integer>> ans = test.levelOrderBottom2(tree);
        System.out.println(ans);
    }

}
